package com.example.jianzhioffer;

/**
 * Created by Quincy on 2018/9/23.
 * 数字在排序数组中出现的次数
 */
public class GetNumberOfK {

    /**
     * 在题目给出的例子中，我们可以先用二分查找算法找到一个3，然后比较3前面的数字是否为3，
     * 如果为3，那么第一次出现3的位置在数组前半段，对前半段进行二分查找。
     * 再比较3后面的数字是否为3，如果为3，那么最后一次出现3的位置肯定在数组的后半段，对后半段进行二分查找。
     * 最后可以得到3第一次出现和最后一次出现的位置，3的次数便可以计算出来，
     * */
    public int GetNumberOfK(int [] array , int k) {
        int count = 0;
        if (null != array && array.length > 0){
            int first = GetFirstK(array, k, 0, array.length-1);
            int last = GetLastK(array, k, 0, array.length-1);
            if ((first > -1) && (last > -1)){
                count = last - first + 1;
            }
        }

        return count;
    }

    private int GetFirstK(int[] array, int k, int start, int end) {
        if (start > end) return -1;
        int mid = (start + end) / 2;
        int midData = array[mid];

        if (midData == k) {
            if ((mid >= 1 && array[mid - 1] != k || mid == 0)) {
                return mid;
            } else {
                end = mid - 1;
            }
        }else if (midData > k){
            end = mid - 1;
        }else {
            start = mid + 1;
        }

        return GetFirstK(array, k, start, end);
    }

    private int GetLastK(int[] array, int k, int start, int end) {
        if (start > end) return -1;
        int mid = (start + end) / 2;
        int midData = array[mid];

        if (midData == k){
            if ((mid + 1 < array.length && array[mid + 1] != k) || mid == array.length - 1)
                return mid;
            else
                start = mid + 1;
        }else if (midData > k){
            end = mid - 1;
        }else {
            start = mid + 1;
        }

        return GetLastK(array, k, start, end);
    }
}
